package cn.ac.ict.fpevaluation.cluster.ap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import cn.ac.ict.fpevaluation.bean.AtomTrajectoryBean;
import cn.ac.ict.fpevaluation.cluster.ICluster;

/**
 * Affinity Propagation
 */
public abstract class AP implements ICluster {
    public List<List<AtomTrajectoryBean>> result = new ArrayList<List<AtomTrajectoryBean>>();
    protected Map<Integer, List<Integer>> allPoint = new HashMap<Integer, List<Integer>>();

    protected List<AtomTrajectoryBean> data;
    protected int trajectoryNum;
    protected ArrayList<Double> pa;
    protected ArrayList<Integer> list;

    /**
     * r(i,k)用来描述点k适合作为数据点i的聚类中心的程度
     */
    protected double[][] r;


    protected double[][] rold;
    protected double[][] a;
    protected double[][] aold;
    protected double[][] m;// r+a
    protected double[][] s;// 相似度矩阵

    // 迭代次数
    protected int maxits = 1000;
    //聚类中心不发生变化次数
    protected int convits = 50;
    // 阻尼系数,主要是起收敛作用
    protected double lamp = 0.5;

    /**
     * 构造函数，传入
     *
     * @param data
     */
    public AP(List<AtomTrajectoryBean> data) {
        this.data = data;
        this.trajectoryNum = this.data.size();
        a = new double[trajectoryNum][trajectoryNum];
        r = new double[trajectoryNum][trajectoryNum];
        rold = new double[trajectoryNum][trajectoryNum];
        aold = new double[trajectoryNum][trajectoryNum];
        m = new double[trajectoryNum][trajectoryNum];
    }

    /**
     * AP启动函数
     *
     * @return
     */
    public List<List<AtomTrajectoryBean>> launch() {
        similarity();
        int count = 0;

        StringBuffer oldM = new StringBuffer();
        for (int i = 0; i < maxits && count < convits; i++) {
            calRes();
            calAvail();
            StringBuffer newM = new StringBuffer();
            for (int k = 0; k < trajectoryNum; k++)
                if (a[k][k] + r[k][k] > 0) // 当(R(k,k)+A(k,k))＞0时认为是一个聚类中心
                    newM = newM.append(k);

            if (newM.toString().equals(oldM.toString())) count++;
            else {
                oldM = newM;
                count = 0;
            }
        }
        //System.out.println("连续迭代" + count + "次聚类中心没有变化");

        for (int i = 0; i < trajectoryNum; i++) {
            for (int j = 0; j < trajectoryNum; j++) {
                m[i][j] = a[i][j] + r[i][j];
            }
        }

        // 利用响应度和可用性综合评价哪个点适于作中心点。
        // 对于点i，使a(i，k)+r(i，k)最大的k即i的中心点，
        // 若k=i，则i本身即中心点。
        for (int i = 0; i < trajectoryNum; i++) {
            double max = Integer.MIN_VALUE;
            int loc = 0;
            for (int j = 0; j < trajectoryNum; j++) {
                if (max < m[i][j]) {
                    max = m[i][j];
                    loc = j;
                }
            }

            if (loc != i) {
                if (allPoint.containsKey(loc)) {
                    allPoint.get(loc).add(i);
                } else {
                    list = new ArrayList<Integer>();
                    list.add(i);
                    allPoint.put(loc, list);
                }
            } else {
                if (!allPoint.containsKey(loc)) {
                    list = new ArrayList<Integer>();
                    allPoint.put(loc, list);
                }
            }
        }

//        System.out.println("聚类数目为:" + allPoint.size());

        for (Entry<Integer, List<Integer>> entry : allPoint.entrySet()) {
            ArrayList<AtomTrajectoryBean> temp = new ArrayList<AtomTrajectoryBean>();
            temp.add(data.get(entry.getKey()));
            for (int i : entry.getValue()) {
                temp.add(data.get(i));
            }

            result.add(temp);
        }

        return result;
    }

    /**
     * 计算相似度矩阵s
     *
     * @throws Exception
     */
    private void similarity() {
        s = calSimilarity(data);

    }

    /**
     * 计算两条原子轨迹间的相似度
     * 需要子类重写
     *
     * @param data
     * @return
     */
    protected abstract double[][] calSimilarity(List<AtomTrajectoryBean> data);

    /**
     * 计算中值
     *
     * @param data
     * @return
     */
    protected double calMidValue(ArrayList<Double> data) {
        // 中值也称中位数，即数据按升序或者降序排列，假如有n个数据，
        // 当n为偶数时，中位数为第n/2位数和第(n+2)/2位数的平均数；
        // 如果n为奇数，那么中位数为第(n+1)/2位数的值。

        Collections.sort(data);

        int size = data.size();

        int mid = size >> 1;

        return (size & 1) == 1 ? data.get(mid) : (data.get(mid) + data.get(mid + 1)) / 2;
    }

    // r(i,k)用来描述点k适合作为数据点i的聚类中心的程度
    private void calRes() {
        for (int i = 0; i < trajectoryNum; i++) {
            double max = Integer.MIN_VALUE;
            for (int k = 0; k < trajectoryNum; k++) {
                for (int j = 0; j < trajectoryNum; j++) {
                    if (j != k) {
                        if (max < a[i][j] + s[i][j]) {
                            max = a[i][j] + s[i][j];
                        }
                    }
                }
                r[i][k] = s[i][k] - max;
                max = Integer.MIN_VALUE;
            }
        }

        for (int i = 0; i < trajectoryNum; i++) {
            for (int j = 0; j < trajectoryNum; j++) {
                r[i][j] = r[i][j] * (1.0 - lamp) + rold[i][j] * lamp;
                rold[i][j] = r[i][j];
            }
        }
    }

    // a(i,k)用来描述点i选择点k作为其聚类中心的适合程度。
    private void calAvail() {
        for (int i = 0; i < trajectoryNum; i++) {
            double sum = 0;
            for (int k = 0; k < trajectoryNum; k++) {
                if (i == k) {
                    for (int j = 0; j < trajectoryNum; j++) {
                        if (j != k) {
                            if (r[j][k] > 0) {
                                sum += r[j][k];
                            }
                        }
                    }
                    a[k][k] = sum;
                    sum = 0;
                } else {
                    for (int j = 0; j < trajectoryNum; j++) {
                        if (j != k && j != i) {
                            if (r[j][k] > 0) {
                                sum += r[j][k];
                            }
                        }
                    }
                    a[i][k] = r[k][k] + sum;
                    if (a[i][k] > 0)
                        a[i][k] = 0;
                    sum = 0;
                }
            }
        }

        for (int i = 0; i < trajectoryNum; i++) {
            for (int j = 0; j < trajectoryNum; j++) {
                a[i][j] = a[i][j] * (1.0 - lamp) + aold[i][j] * lamp;
                aold[i][j] = a[i][j];
            }
        }
    }
}
